package treeDemo;

import java.util.ArrayList;
import java.util.LinkedList;


/**
 * 
 * 二叉树按层遍历打印
 * @author zyj 2018-4-28 15:38:40
 * 
 * https://blog.csdn.net/qq_27703417/article/details/70957332
 * 
 * 
 * 题目：
 * 有一棵二叉树，请设计一个算法，按照层次打印这棵二叉树。给定二叉树的根结点root，
 * 请返回打印结果，结果按照每一层一个数组进行储存，所有数组的顺序按照层数从上往下，
 * 且每一层的数组内元素按照从左往右排列。保证结点数小于等于500。
 * 
 * 思路：
 * 对于二叉树，除了先序遍历、中序遍历、后序遍历之外，BFS（深度优先搜索）
 * 常用的遍历方式还有按层遍历，即一层一层地进行遍历，通常还要求在遍历时携带行的信息，
 * 例如一层遍历完后要求打印换行符或者每一层都打印行号。
 * 
 * 对于按层遍历的理解：
 * 1.按层遍历属于针对二叉树的宽度优先遍历问题（DFS）
 * 2.对于图的宽度优先遍历，常常使用队列结构来解决问题
 * 3.面试中，按层遍历常常对换行有所要求
 * 
 * 步骤：
 * 1、队列从上到下，从左到右 依次加入所有的节点
 * 2、node 保存当前加入的队列的最后一个节点
 *    nLastNodeb表示下一层的最后一个节点
 *    if(queue.poll()==nLastNodeb){
 *    		1、换行;
 *    		//因为队列已经加入了下一行的所有元素了，下一行最后一个可以得到。
 *    		2、nLastNodeb=node;
 *    } 
 * 3、LinkedList 队列 用于存储所有Node
 * 	Arraylist<ArrayList<>> 用于表示层级
 * 	
 * 	|--
 * 	|---
 *  |---
 *
 * 
 * 
 *
 */
public class TreeSetPrint1 {
	
public static void main(String[] args) {


}
	
	 public static int[][] printTree(TreeNode root) {  
	        //①创建一个队列：使用链表LinkedList来实现队列  
	        LinkedList<TreeNode> queue=new LinkedList<>();  
	        //创建集合results用来存放遍历过的结点，每一层对应一个集合，整体结果也是一个集合，于是集合里面放集合  
	        ArrayList<ArrayList<TreeNode>> results=new ArrayList<>();  
	        //②创建临时变量temp表示当前表示当前正在访问的结点  
	        TreeNode temp=root;  
	        //③创建遍历指针last表示下一层的最后结点，nlast表示当前now正在访问的结点（不是遍历是访问），注意初始值  
	        TreeNode last=root;  
	        TreeNode nlast=null;  
	        //创建一个集合levelList表示每一层对应的集合，用来存放一层的结点  
	        ArrayList<TreeNode> levelList=new ArrayList<>();  
	        //③先将根结点放入到队列中  
	        queue.add(root);  
	        //④开始循环：弹出结点--记录--放入左右结点--判断是否到层最后  
	        while(queue.size()!=0){  
	            //弹出队列，这是正在遍历的结点，放入每一层的集合  
	            temp=queue.poll();  
	            levelList.add(temp);  
	            //压入左右2个子节点,注意要同时移动更新nlast  
	            if(temp.left!=null){  
	                queue.add(temp.left);  
	                nlast=temp.left;  
	            }  
	            if(temp.right!=null){  
	                queue.add(temp.right);  
	                nlast=temp.right;  
	            }  
	            //判断是否到边  
	            //如果到边则换行，更新  
	            if(temp==last){  
	                //表示到边，进行换行操作，同时更新last  
	                results.add(levelList);  
	                levelList=new ArrayList<>();  
	                
	                System.out.println("下一行最后一个数："+last.val);
	                //常识：levelList只是一个变量名称，只是中间桥梁，results通过levelList已经创建了指向集合真正位置的地址  
	                last=nlast;  
	                System.err.println("下一行最后一个数："+last.val);
	            }  
	        }  
	        //双重遍历将结果取出放入到二维数组中  
	        int[][] results2=new int[results.size()][];  
	        for(int i=0;i<results.size();i++){  
	            results2[i]=new int[results.get(i).size()];  
	            for(int j=0;j<results2[i].length;j++){  
	                results2[i][j]=results.get(i).get(j).val;  
	            }  
	        }  
	        //返回结果  
	        return results2;  
	    }  
}


